package com.ww.springboot.boot.algorithm.leetcode1;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;


/**
 * 描述：
 *
 * @author 🧑 ‍wanwei
 * @since 2022-04-18 09:00
 */
public class BP438找到字符串中所有字母异位词 {

    public static void main(String[] args) {

        List<Integer> list = findAnagrams("abab", "ab");
        System.out.println(list);
    }

    /**
     * 1.滑动窗口 边滑动边判断
     * 2.怎么判断是否异位词?
     * 将p按照字母顺序重排 然后滑动窗口生成的字符串也按照字母顺序重排 再判断两字符串是否相同
     * <p>
     * 优化 不需要生成字符串 直接比较数组即可 数组最大长度为26;
     * <p>
     * 进一步优化 不需要每次都重新比较数组？？？？还没想出来解决办法
     *
     * @param s
     * @param p
     * @return
     */
    public static List<Integer> findAnagrams(String s, String p) {
        List<Integer> list = new ArrayList<>();
        if (s.length() < p.length()) {
            return list;
        }
        int[] arrayP = new int[26];
        int[] arrayNew = new int[26];
        for (int i = 0; i < p.length(); i++) {
            arrayP[p.charAt(i) - 'a']++;
            arrayNew[s.charAt(i) - 'a']++;
        }

        if (Arrays.equals(arrayP, arrayNew)) {
            list.add(0);
        }
        for (int i = p.length(); i < s.length(); i++) {
            arrayNew[s.charAt(i) - 'a']++;
            arrayNew[s.charAt(i - p.length()) - 'a']--;
            if (Arrays.equals(arrayP, arrayNew)) {
                list.add(i - p.length() + 1);
            }
        }
        return list;
    }

}
